package cn.itsource.linkedlist;

/**
 *	1. 数据结构：就是数据保存的方式。
 *
 *	2. 为什么要学习？
 *		就是为了在不同的需求下，更好的选择合适的数据类型，可以提高效率
 *
 *	3. 数据结构都有哪些？
 *			1. List 有序（存入和取出）可重复集合		
 *				1. ArrayList	基于数组，适用于查询和修改较多
 *				2. LinkedList	基于双向链表，适用于增删插
 *					Stack（栈，先进后出 FILO）
 *				3. Vector 线程安全的ArrayList
 *				
 *			2. Set	无序（存入和取出）不可重复集合
 *				1. HashSet	
 *				2. TreeSet
 *				3. LinkedHashSet
 *
 *			3. Map	键值对（Entry<Key,Value>）集合
 *				1. HashMap
 *				2. TreeMap
 *				3. LinkedHashMap
 *				4. ConcurrentHashMap
 *				5. HashTable
 *
 *			4. Queue 队列  （订单排队，任务队列）
 *				1. Queue	FIFO先进先出	
 *				2. Deque	双端队列 ，两端进出
 *					Stack	栈，FILO
 *					
 *			5. Tree 树状结构 （菜单和子菜单，上下级关系）
 *				1. 二叉树
 *						红黑树（自平衡机制，为了提高查询效率）
 *
 *				2. 多叉树
 *
 *	4. 能够保存数据的方式有哪些？
 *		1. 变量（保存一个）
 *		2. 数组（保存多个）
 *
 *	5. 需求：	基于链表，增删插快
 *			基于变量（对象）：可以保存多个不同类型的数据
 *			
 *				1. 可以任意添加任意类型的数据 void add(Object obj)
 *				2. 可以记录当前数据的个数 int size()
 *				3. 可以打印当前数据结构的对象 toString()，格式如下：[值1，值2.。。。。]
 *
 *				4. 查询指定下标的元素  Object searchByIndex(int index)
 *				5. 查询指定的元素第一次出现的位置  int searchByElement(Object ele);
 *			
 *
 *				根据下标查询当前的节点对象 Node searchNodeByIndex(int index)(重要方法)
 *
 *				6. 修改指定下标处的元素  void updateByIndex(int index,Object obj)
 *				7. 删除指定下标处的元素，返回删除的元素  	Object deleteByIndex(int index)
 *				8. 删除的首次出现的指定元素     void deleteByElement(Object ele)
 *				9. 插入指定下标处一个指定元素 void insertByIndex(int index,Object obj)
 *					
 *				10.将对象中所有元素清空 void clear();
 *				11.创建对象，可以直接传入一个参数初始化
 */		
public class LinkedListDemo {
	/**保存第一个Node对象的地址*/
	private Node first;
	/**保存元素个数*/
	private int size;
	
	public LinkedListDemo() {
	}
	
	/**
	 * 11.创建对象，可以直接传入一个参数初始化
	 * @param obj
	 */
	public LinkedListDemo(Object obj){
		add(obj);
	}
	
	/**
	 * 1. 可以任意添加任意类型的数据 void add(Object obj)
	 * @param obj
	 */
	public void add(Object obj){
		/*
		 * 	第一次添加：
				1.先创建一个Node对象，赋值字段value = 值；
				2.将第一个对象的地址赋值给first
				
			第n个的时候，怎么添加：
				遍历整个链表，查看当前元素的next字段是否为null，只有是null，证明是最后一个元素，
				直接将新创建Node对象地址赋值给 该Node的next字段
			
			size++
			遍历：结合画图
		 */
		//将添加的数据，保存到新创建的Node对象中
		Node node = new Node(obj);
		if (first == null) {//说明第一个元素还没有添加
			first = node;//将第一个Node对象赋值给first保存
		} else {
			//声明一个临时变量，保存遍历到的Node元素地址
			Node temp = first;//先从第一个开始遍历
			while (temp.next != null) {//如果当前元素的next不为null，说明不是最后一个元素
				//将指针后移一位，即，将下一个元素地址赋值给临时变量temp
				temp = temp.next;
			}
			//循环完毕后，一定是最后一个元素了，因为next字段是null了，这是只需要将新创建的Node对象地址赋值给next字段即可
			temp.next = node;
		}
		//元素个数+1
		size++;
	}
	
	/**
	 * 3. 可以打印当前数据结构的对象 toString()，格式如下：[值1，值2.。。。。]
	 */
	public String toString() {
		//准备一个字符串，进行元素的value拼接
		StringBuilder sb = new StringBuilder("[");
		//如果当前没有元素，就直接返回一对[]
		if (size == 0) {
			return sb.append("]").toString();
		}
		//如果当前有元素，就要遍历链表，然后每遍历一个元素，就拼接一个元素的value值，最后一个不要拼接,
		Node temp = first;//声明一个临时变量，保存遍历到的元素地址，遍历从第一个开始
		/*
		 * while (temp != null) {//遍历到的元素存在，就拼接value值
			//拼接value值和,
			sb.append(temp.value);
			//判断当前遍历到的元素是不是最后一个元素，如果不是才拼接，
			if (temp.next != null) {
				sb.append(",");
			}
			//将指针后移一位，即，将下一个元素地址赋值给临时变量temp
			temp = temp.next;
		}
		因为知道元素个数size，所有可以用for循环，只要遍历到倒数第二个元素，再拼接最后一个元素的value即可
		*/
//		//循环完毕后，一定是最后一个元素了
//		return sb.append("]").toString();
		
		for (int i = 0; i <= size-2; i++) {
			//先拼接上当前元素的vlaue值和，
			sb.append(temp.value).append(",");
			temp = temp.next;
		}
		//循环完毕后，一定是倒数第2个元素了，再拼接最后一个元素的value即可
		return sb.append(temp.value).append("]").toString();
	}
	
	/**
	 * 校验下标合法性
	 * @param index
	 * @throws IllegalArgumentException
	 */
	private void checkIndex(int index)throws IllegalArgumentException {
		if (index > size-1 || index < 0) {
			throw new IllegalArgumentException("请注意，下标范围：[0," + (size-1) + "]");//非法参数异常，给调用者提示
		}
	}
	
	/**
	 * 根据下标查询当前的节点对象 Node searchNodeByIndex(int index)
	 * @param index
	 * @return
	 * @throws IllegalArgumentException
	 */
	private Node searchNodeByIndex(int index) throws IllegalArgumentException{
		//校验下标合法性
		checkIndex(index);
		//遍历当前链表
		Node temp = first;//从第一个元素开始遍历
		//遍历的次数是< index
		for (int i = 0; i < index; i++) {
			//将指针后移一位，即，将下一个元素地址赋值给临时变量temp
			temp = temp.next;
		}
		//循环结束后，index处的Node对象就是temp
		return temp;
	}
	
	/**
	 * 4. 查询指定下标的元素  Object searchByIndex(int index)
	 * @param index
	 * @return
	 * @throws IllegalArgumentException 
	 */
	public Object searchByIndex(int index) throws IllegalArgumentException{
		//直接调用上面的Node searchNodeByIndex(int index)方法获取index处的Node对象
		Node node = searchNodeByIndex(index);
		return node.value;//直接将Node对象的value值返回
	}
	
	/**
	 *  5. 查询指定的元素第一次出现的位置  int searchByElement(Object ele);
	 * @param ele
	 * @return
	 */
	public int searchByElement(Object ele){
		//判断当前链表是否为null，如果为null，直接返回-1
		if (first == null) {
			return -1;
		}
		//因为当前ele有可能为null，所以要分情况遍历链表，如果是null用==比较，如果不是null，用equals比较
		if (ele == null) {
			Node temp = first;//从第一个元素开始遍历
			for (int i = 0; i < size; i++) {
				if (ele == temp.value) {
					return i;
				}
				temp = temp.next;//将下一个元素的地址赋值给temp
			}
		} else {
			Node temp = first;//从第一个元素开始遍历
			for (int i = 0; i < size; i++) {
				if (ele.equals(temp.value)) {
					return i;
				}
				temp = temp.next;//将下一个元素的地址赋值给temp
			}
		}
		//循环结束，表示已经未找到
		return -1;
	}
	
	/**
	 * 6. 修改指定下标处的元素  void updateByIndex(int index,Object obj)
	 * @param index
	 * @param obj
	 * @throws IllegalArgumentException 
	 */
	public void updateByIndex(int index,Object obj) throws IllegalArgumentException{
		//校验数组下标范围
		checkIndex(index);
		//调用查询指定下标的Node节点 Node searchNodeByIndex(int index)
		Node node = searchNodeByIndex(index);
		//直接将查询到的节点对象value值赋值为obj
		node.value = obj;
	}
	
	
	/**
	 * 7. 删除指定下标处的元素，返回删除的元素  	Object deleteByIndex(int index)
	 * @param index
	 * @return
	 * @throws IllegalArgumentException
	 */
	public Object deleteByIndex(int index) throws IllegalArgumentException{
		/*//声明一个变量保存当前元素的value值
		Object value = null;
		//先判断是否是第一个元素，直接将第二个的地址赋值给first即可
		if (index == 0) {
			value = first.value;
			first = first.next;
			//元素个数-1
			size--;
			return value;
		}
		//先查询上一个元素Node对象
		Node prefix = searchNodeByIndex(index - 1);
		//先查询当前元素Node对象
		Node now = searchNodeByIndex(index);
		
		value = now.value;
		//只要将当前元素now的next值赋值给上一个元素prefix的next
		prefix.next = now.next;
		//元素个数-1
		size--;
		return value;//将删除的对象value值返回
		也可以用下面的方式
		 */		
		//校验数组下标范围
		checkIndex(index);
		//如果是删除第一个元素，直接将第2个元素的地址赋值给first即可
		Node now = null;
		if (index == 0) {
			//保存第一个元素
			now = first;
			//将第二个元素地址赋值给first
			first = first.next;
		} else {
			//查询出index上一个节点
			Node prefix = searchNodeByIndex(index-1);
			//查询出要删除的index处的节点
			now = searchNodeByIndex(index);
			//将上一个节点的next赋值为index的next（就是index后一个的地址）
			prefix.next = now.next;
			//元素个数-1
		} 
		size--;
		return now.value;
	}
	
	/**
	 * 8. 删除的首次出现的指定元素     void deleteByElement(Object ele)
	 * @param ele
	 * @throws IllegalArgumentException 
	 */
	public void deleteByElement(Object ele) throws IllegalArgumentException{
		//调用方法查找该元素下标，如果下标是-1，表示该链表中没有该元素，直接结束方法
		int index = searchByElement(ele);
		if (index < 0) {
			return;
		}
		//调用上面根据指定下标删除元素方法
		deleteByIndex(index);
	}
	
	/**
	 * 9. 插入指定下标处一个指定元素 void insertByIndex(int index,Object obj)
	 * 跟删除方法类似，通过画图得知，只需要将index上一个元素的next赋值为当前插入的元素地址，将插入的元素next赋值为index处元素的地址即可
	 * @param index
	 * @param obj
	 * @throws IllegalArgumentException 
	 */
	public void insertByIndex(int index,Object obj) throws IllegalArgumentException{
		//校验数组下标范围
		checkIndex(index);
		//创建一个Node对象，保存obj的值
		Node node = new Node(obj);
		//如果是插入的下标是0，直接将第first元素的地址赋值给新插入的元素next，将first赋值为新插入的元素地址即可
		if (index == 0) {
			//将原来的第一个元素地址赋值给新插入的元素next保存
			node.next = first;
			//将first赋值为新插入的元素node地址即可
			first = node;
		} else {
			//查询出index上一个节点
			Node prefix = searchNodeByIndex(index-1);
			//查询出插入index处的节点
			Node now = searchNodeByIndex(index);
			//将新插入的节点node的next赋值为index处的now的地址
			node.next = now;
			//将是一个节点的next赋值为新插入的node地址
			prefix.next = node;
		} 
		size++;
	}
	
	/**
	 * 10.将对象中所有元素清空 void clear();
	 */
	public void clear(){
		//直接将第一个元素赋值null即可
		first = null;
		//元素个数归零
		size = 0;
	}
	
	/**
	 * 2. 可以记录当前数据的个数 int size()
	 * @return
	 */
	public int size(){
		return size;
	}
	
	/**
	 * 内部类Node，只用来服务LinkedList，用了保存数据和下一个Node对象的地址的
	 */
	private class Node{
		/**保存数据的字段*/
		Object value;
		/**保存下一个Node对象的地址的字段*/
		Node next;
		/**
		 * 有参构造
		 * @param value
		 */
		public Node(Object value) {
			super();
			this.value = value;
		}
	}
}
